//
// Created by wdq on 22-9-18.
//
#include <iostream>
#include <cstring>
using namespace std;

template<typename KeyType, typename ValueType>
struct Pair {
    KeyType key;
    ValueType value;
    Pair *next;

    Pair() : next(nullptr) {}

    Pair(KeyType key, ValueType value, Pair *next = nullptr) : key(key), value(value), next(next) {}

    friend ostream &operator<<(ostream &os, const Pair &pair) {
        os << "key: " << pair.key << " value: " << pair.value;
        return os;
    }


};

template<typename KeyType, typename ValueType>
struct HashMap {
    Pair<KeyType, ValueType> *head;
    int capacity;

    explicit HashMap(int capacity = 10) : capacity(capacity) {
        head = new Pair<KeyType, ValueType>[capacity];
        memset(head,NULL, sizeof(Pair<KeyType,ValueType>)*capacity);
    }

    ~HashMap() {
        delete[]head;
    }

    Pair<KeyType, ValueType> *find(KeyType key) {
        int i = hashcode(key) % capacity;
        auto temp = &head[i];
        for (auto item = head[i].next; item != nullptr; item = item->next) {
            if (item->key == key) {
                return item;
            }
            temp = item;
        }
        return temp;

    }

    Pair<KeyType, ValueType> *get(KeyType key) {
        int i = hashcode(key) % capacity;
        for (auto item = head[i].next; item != nullptr; item = item->next) {
            if (item->key == key) {
                return item;
            }
        }
        return nullptr;
    }

    int hashcode(string p) {
        int hash = 0;
        for (int i = 0; p[i] != 0; i++) {
            hash = hash * 131 + p[i];
        }
        return hash;
    }

    void put(KeyType key, ValueType value) {
        auto item = find(key);
        if (item->key == key) {
            item->value = value;
        } else {
            item->next = new Pair<KeyType, ValueType>(key, value);
        }
    }

    void output() {
        for (int i = 0; i < capacity; i++) {
            auto item = head[i].next;
            printf("hashcode: %d  ", i);
            while (item != nullptr) {
                cout << " < " << item->key << " , " << item->value << " > ";
                item = item->next;
            }
            printf("\n");
        }
    }

    void remove(KeyType key) {
        int i = hashcode(key) % capacity;
       auto temp = &head[i];
        auto item = head[i].next;
        for (; item != nullptr && item->key != key; item = item->next) {
            temp = item;
        }
        if (item == nullptr) {
            return;
        }
        temp->next = item->next;
        delete item;


    }
};

int main() {
    HashMap<const char *, const char *> map(6);
    map.put("wdq", "吴道清");
    map.put("kmm", "康民明");
    map.put("lk", "冷阔");
    map.put("yjj", "杨俊杰");
    map.put("whr", "王华瑞");
    map.put("hmy", "黄明洋");
    map.put("wdq", "nb");
    map.remove("wdq");
    map.output();
    map.put("wdq", "吴道清");
    cout << endl;
    map.output();

    return 0;
}